Solving 10385 - Duathlon (Ternary search)
[andmenj-acm.git] / 11116 - Babel towers / 11116.2.cpp
blobd5efb0b79be6c1cb0f807dc548cff15fc892eef8
1 /*
2 Problem: 11116 - Babel towers
3 (From the UVa Online Judge)
5 Author: Andrés Mejía-Posada
6 Date: April 20/2008
7 */
9 #include <iostream>
10 #include <iomanip>
11 #include <cmath>
12 #include <algorithm>
13 #include <vector>
15 using namespace std;
17 const double EPS = 10E-9;
19 struct disc{
20 double x, y, r;
21 disc(){}
22 disc(double X, double Y, double R) : x(X), y(Y), r(R){}
25 //Represents a mass "m" centered at point ("x", "y")
26 struct center{
27 double x, y, m;
28 center(){}
29 center(double X, double Y, double M) : x(X), y(Y), m(M){}
30 center &operator = (const center &b){
31 x = b.x;
32 y = b.y;
33 m = b.m;
34 return *this;
39 //Returns the new mass formed by combining both masses "a" and "b" into a puntual mass.
40 center operator | (const center &a, const center &b){
41 center r;
42 r.x = (a.x * a.m + b.x * b.m) / (a.m + b.m);
43 r.y = (a.y * a.m + b.y * b.m) / (a.m + b.m);
44 r.m = a.m + b.m;
45 return r;
48 //For debugging
49 ostream& operator<<( ostream& out, const center &c) {
50 out << setprecision(2) << "(" << c.x << ", " << c.y << ", " << c.m << ")";
51 return out;
54 //For debugging
55 ostream& operator<<( ostream& out, const disc &c) {
56 out << setprecision(2) << "(" << c.x << ", " << c.y << ", " << c.r << ")";
57 return out;
61 //True if the center of mass "C" is outside of the base of disc "D"
62 inline bool outside(const center &c, const disc &d){
63 return fabs((c.x-d.x)*(c.x-d.x) + (c.y-d.y)*(c.y-d.y)) > d.r*d.r - EPS;
66 int main(){
67 int n;
68 while (cin >> n && n){
70 vector<disc> d(n);
71 for (int i=0; i<n; ++i){
72 double x, y, r;
73 cin >> x >> y >> r;
74 d[i] = disc(x, y, r);
78 int k;
79 bool ok = true;
80 for (int j=1; j < n && ok; ++j){
81 center c(d[j].x, d[j].y, d[j].r * d[j].r);
83 for (int i=j-1; i >= 0 && ok; --i){
84 if (outside(c, d[i])){
85 ok = false;
86 k = j;
88 c = c | center(d[i].x, d[i].y, d[i].r*d[i].r);
92 cout << (ok?"F":"Unf") << "easible";
93 if (!ok) cout << " " << k;
94 cout << endl;
97 return 0;